package com.neusoft.question;

import java.util.Arrays;

/**
 * @author LYW
 *
 */

public class SortAlgorithm {

	public static void main(String[] args) {
		//定义一个数组
//		int[] iArray1 = { 20, 5, 23, 89, 78, 2, 66, 9, 2, 0 };


		// 调用排序算法
		// 选择排序
		// iArray1=selectSort(iArray1);
		// 冒泡排序
		// bubbleSort(iArray1);
		// 插入排序
		//iArray1 = insertSort1(iArray1);
		//iArray1 = insertSort0(iArray1);
//		 insert_sort(iArray1, 10);
//		print1DArray(iArray1);
		int leng = 200;
		int[] arr2= new int[leng];
		//定义一个数组 ，赋随机数		
		for(int i=0;i<arr2.length;i++) {
			
				arr2[i]=(int)(Math.random()*3000);
		}
		int[] arr3 = Arrays.copyOf(arr2, leng);
		int[] arr4 = Arrays.copyOf(arr2, leng);
		int[] arr5 = Arrays.copyOf(arr2, leng);
		int[] arr6 = Arrays.copyOf(arr2, leng);
		System.out.println("冒泡排序");
		//打印数组
//		print1DArray(arr2);
		//希尔排序
		//shellSort(arr2);
		//快速排序
		//quickSort(arr2, 0, arr2.length-1);
//		quickSort2(arr2, 0, arr2.length-1);
		//冒泡排序
		//bubbleSort(arr2);
		//优化有序数列的冒泡排序
		bubbleSort2(arr2);
		//打印数组
//		print1DArray(arr2);
		
		System.out.println("希尔排序");
//		print1DArray(arr3);
		//希尔排序
		shellSort(arr3);
//		print1DArray(arr3);
		System.out.println("插入排序");
//		print1DArray(arr4);
		//希尔排序
		insertSort1(arr4);
//		print1DArray(arr4);
		System.out.println("选择排序");
		//选择排序
		selectSort(arr5);
		System.out.println("快速排序");
		quickSort(arr6, 0, arr6.length-1);
		print1DArray(arr6);
		
	}
	
	
	public static void quickSort2(int a[],int l,int r){
	    //这句话是出错的地方，一直调用没有返回
		if(l>=r)
	       return;

	     int i = l; int j = r; int key = a[l];//选择第一个数为key

	     while(i<j){

	         while(i<j && a[j]>=key)//从右向左找第一个小于key的值
	             j--;
	         if(i<j){
	             a[i] = a[j];
	             i++;
	         }

	         while(i<j && a[i]<key)//从左向右找第一个大于key的值
	             i++;

	         if(i<j){
	             a[j] = a[i];
	             j--;
	         }
	     }
	     //i == j
	     a[i] = key;
	     quickSort2(a, l, i-1);//递归调用
	     quickSort2(a, i+1, r);//递归调用
	 }
	
	
	/**
	 * 快速排序
	 */
	private static void quickSort(int[] array,int left,int right) {
		//定义基准值
		int key;
		//定义左侧起始下标，序列中第一个元素
		int i =left;
		//定义右侧起始下标，序列中最后一个元素
		int j=right;
		if(left>=right) {
			return;
		}
			
		//假设基准值为数组序列中第一个元素，即left
		key=array[left];
		//在i到j范围内循环
		while(i<j) {
		
		//递减j寻找小于key的值
		while(i<j&&array[j]>key) {
			j--;
		}
		//递减之后的j仍比i大，就将j给i
		if(i<j) {
			array[i]=array[j];
			i++;
		}
		
		
		//递增i寻找大于key的值
		while(i<j&&array[i]<=key) {
			i++;
			
		}
		//如果i比j小 将i赋给j
		if(i<j) {
			array[j]=array[i];
			j--;
			
		}
		
		
		
		}
		//i==j	
			array[i]=key;
		quickSort(array,left,i-1);
		quickSort(array,i+1,right);
		
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	/**
	 * 希尔排序算法
	 */
	public static void shell_sort(int array[],int lenth){

		   int temp = 0;
		   int incre = lenth;

		   while(true){
		       incre = incre/2;

		       for(int k = 0;k<incre;k++){    //根据增量分为若干子序列

		           for(int i=k+incre;i<lenth;i+=incre){

		               for(int j=i;j>k;j-=incre){
		                   if(array[j]<array[j-incre]){
		                       temp = array[j-incre];
		                       array[j-incre] = array[j];
		                       array[j] = temp;
		                   }else{
		                       break;
		                   }
		               }
		           }
		       }

		       if(incre == 1){
		           break;
		       }
		   }
		}
	
	/**
	 * 希尔排序  自己写的  终于写对了
	 * 问题还是在于引入插入排序的算法写的有问题
	 * 只要根据增量对应修改就可以了
	 * 	 */
	private static void shellSort(int[] arr) {
		//定义增量
		int incre=arr.length;
		//定义交换次数
		int count=0;
		//while循环
		while(true) {
			//增量逐渐变小
			incre=incre/2;
			//循环增量范围
			for(int i=0;i<incre;i++) {
				//做插入排序
				for(int j=i;j<arr.length-incre;j+=incre) {
					for(int k=j+incre;k>i;k-=incre) {
						if(arr[k]<arr[k-incre]) {
							int temp=arr[k];
							arr[k]=arr[k-incre];
							arr[k-incre]=temp;
							count++;
						}
					}
				}
			}
			if(incre<=1) {
				break;
			}
			
		}
		System.out.println("希尔排序的交换次数为"+count);
		
	}
	
	
	
	
	
	
	
	
	
	
	
	
	/**
	 * 插入排序 一般来说，插入排序都采用in-place在数组上实现。
	 * 具体算法描述如下： 
	 * 从第一个元素开始，该元素可以认为已经被排序；
	 * 取出下一个元素，在已经排序的元素序列中从后向前扫描； 
	 * 如果该元素（已排序）大于新元素，将该元素移到下一位置；
	 * 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置； 
	 * 将新元素插入到该位置后；
	 *  重复步骤2~5。
	 * 
	 * 
	 */
	
	public static void  insert_sort(int array[],int lenth){

		   int temp;

		   for(int i=0;i<lenth-1;i++){
		       for(int j=i+1;j>0;j--){
		           if(array[j] < array[j-1]){
		               temp = array[j-1];
		               array[j-1] = array[j];
		               array[j] = temp;
		           }else{         //不需要交换
		               break;
		           }
		       }
		   }
		   for(int j=0;j<array.length;j++) {
			   System.out.println(array[j]+" ");
		   }
		}
	
	
	
	
	
	
	private static int[] insertSort0(int[] array) {
		//
		int preIndex, current;
		//

		// 输出程序开始
		System.out.println("begin insert sort:");

		// 从第1个元素便利到倒数第1个元素
		for (int i = 0; i < array.length-1; i++) {
			// 存储即将插入的元素
			preIndex = i;
			current = array[i+1];

			while (preIndex >= 0 && array[preIndex] > current) {
				array[preIndex + 1] = array[preIndex];
				preIndex--;
			}
			array[preIndex + 1] = current;

			// 每轮循环完成后输出数组
//			for (int k = 0; k < array.length; k++) {
//				System.out.print(array[k] + " ");
//			}
//			System.out.println();

		}
		return array;

	}
	
	
	
	
	//越改越错，重新理思路重新写
	private static void insertSort1(int[] array) {
		//统计交换次数
		int count=0;
		for (int i = 0; i < array.length - 1; i++) {

			for (int j = i; j >= 0; j--) {

				if (array[j + 1] < array[j]) {
					int temp2 = array[j];
					array[j] = array[j+1];
					array[j+1] = temp2;
					count++;
					//System.out.println("array["+j+"]="+array[j]);
					//System.out.println("array["+(j+1)+"]="+array[j+1]);
				} else {

					break;
				}

			}

		}
		System.out.println("插入排序的交换次数为"+count);
	}
//	
	
	
	private static void bubbleSort2(int[] array) {
		//输出提示程序开始
		System.out.println("begin bubble sort2：");
		//定义最大值
		int max=0;
		//定义循环因子
		int i,j,k;
		//统计交换次数
		int count=0;
		//标志位，判断是否有序（如果本轮循环中没有发生交换为有序）
		boolean isSorted;
		//for循环执行
		for(i=0;i<array.length;i++) {
			//设有序
			isSorted=true;
			for(j=0;j<array.length-i-1;j++) {
				//如果下标为j的数比j+1大 ，交换两个数
				if(array[j]>array[j+1]) {
					k=array[j+1];
					array[j+1]=array[j];
					array[j]=k;
					//如果发生交换，证明数列还不是有序的
					isSorted = false;
					count++;
				}
			}
			//退出内层循环后，判断是否有序
			if(isSorted) {
				break;
			}
		}
		System.out.println("bubble2比较次数为"+count);
	}
	
	
	
	
	
	/**
	 * 冒泡排序：
	 * 重复走访临近的两个元素，进行比较找，最大值放到最后面
	 * 重复走访临近两个元素，除了最后一个，进行比较找，奖最大值放到最后
	 * 重复执行上一步
	 * 直到第一个元素和第二个元素比较
	 * 
	 */
	/**
	 * 算法 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
	 * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数； 针对所有的元素重复以上的步骤，除了最后一个；
	 * 重复步骤1~3，直到排序完成。
	 */
	 
	
	private static void bubbleSort(int[] array) {
		//输出提示程序开始
		System.out.println("begin bubble sort：");
		//定义最大值
		int max=0;
		//定义循环因子
		int i,j,k;
		//统计比较次数
		int count=0;
		
		//for循环执行
		for(i=0;i<array.length;i++) {
			for(j=0;j<array.length-i-1;j++) {
				//如果下标为j的数比j+1大 ，交换两个数
				if(array[j]>array[j+1]) {
					k=array[j+1];
					array[j+1]=array[j];
					array[j]=k;
				}
				count++;
			}
		}
		System.out.println("bubble1比较次数为"+count);
	
				
	}
	

	
	
	
	

	/**
	 * 选择排序算法
	 * 循环遍历数组0-length，再循环遍历i-length,选出最小值 与下标为i的元素交换，遍历一次交换一次
	 */
	
	
	/**
	 * @param iArray
	 * @return
	 * 算法
	 * n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
	 * 初始状态：无序区为R[1..n]，有序区为空；
	 * 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。
	 * 该趟排序从当前无序区中-选出关键字最小的记录 R[k]，
	 * 将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)
	 * 分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
	 * n-1趟结束，数组有序化了。
	 */
	private static void selectSort(int[] iArray) {
		// 定义一个数组 进行排序
		
		System.out.println("begin select Sort");
		// 交换次数
		int iSwap = 0;
		// 记录最小值下标
		int iMin_index;
		int i, j;
		// 从第一个数据遍历到最后一个元素
		for (i = 0; i < iArray.length; i++) {
			// 从i遍历到j，将最小的值交换给iArray[i]
			// 设最小值得下标为i
			iMin_index = i;

			for (j = i + 1; j < iArray.length; j++) {
				if (iArray[j] < iArray[iMin_index]) {
					// 记录
					iMin_index = j;

				}
			}
			//？ 和 ？交换
			//System.out.println(iArray[i] + "和" + iArray[iMin_index] + "交换");
			
			// 这个异或交换如果不加if语句可能把自己清零
			// if(i!=iMin_index) {
			// iArray[i] ^= iArray[iMin_index];
			// iArray[iMin_index] ^= iArray[i];
			// iArray[i] ^= iArray[iMin_index];
			// iSwap++;
			// }
			
			// 用第三方进行交换
			if(i!=iMin_index){
				int k = iArray[i];
				iArray[i] = iArray[iMin_index];
				iArray[iMin_index]= k;
				iSwap++;
			}
			//第几次排序得到？
			//System.out.println("第" + (i + 1) + "次排序得到" + iArray[i]);

		}
		// 循环输出数组内容
//		for (i = 0; i < iArray.length; i++) {
//			System.out.print(iArray[i] + " ");
//		}
//		System.out.println(" ");
		System.out.println("选择排序的交换次数" + iSwap);
		//System.out.println("end");
	}





/**
 * 重载方法   overload
 * @param array
 */
// 定义打印一维数组的方法-整型
private static void print1DArray(int[] array) {
	// 输出提示信息
	System.out.println("==打印数组==");
	// 遍历输出数组
	//System.out.println("排序后数组为：");
	for (int i = 0; i < array.length; i++) {
		System.out.print(array[i] + "  ");
	}
	System.out.println();
}

// 定义打印一维数组的方法-字符型
private static void print1DArray(char[] array) {
	// 输出提示信息
	System.out.println("==打印数组==");
	// 遍历输出数组
	System.out.println("排序后数组为：");
	for (int i = 0; i < 10; i++) {
		System.out.print(array[i] + "  ");
	}
	System.out.println();
}

// 定义打印一维数组的方法-浮点型
private static void print1DArray(double[] array) {
	// 输出提示信息
	System.out.println("==打印数组==");
	// 遍历输出数组
	System.out.println("排序后数组为：");
	for (int i = 0; i < 10; i++) {
		System.out.print(array[i] + "  ");
	}
	System.out.println();
}

// 定义打印一维数组的方法-字符串
private static void print1DArray(String[] array) {
	// 输出提示信息
	System.out.println("==打印数组==");
	// 遍历输出数组
	System.out.println("排序后数组为：");
	for (int i = 0; i < 10; i++) {
		System.out.print(array[i] + "  ");
	}
	System.out.println();
}
}
